﻿// LCP 14. 切分数组.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <unordered_map>


using namespace std;
/*
https://leetcode.cn/problems/qie-fen-shu-zu/description/


给定一个整数数组 nums ，小李想将 nums 切割成若干个非空子数组，使得每个子数组最左边的数和最右边的数的最大公约数大于 1 。
为了减少他的工作量，请求出最少可以切成多少个子数组。

示例 1：
输入：nums = [2,3,3,2,3,3]
输出：2
解释：最优切割为 [2,3,3,2] 和 [3,3] 。第一个子数组头尾数字的最大公约数为 2 ，第二个子数组头尾数字的最大公约数为 3 。

示例 2：
输入：nums = [2,3,5,7]
输出：4
解释：只有一种可行的切割：[2], [3], [5], [7]


限制：
1 <= nums.length <= 10^5
2 <= nums[i] <= 10^6
*/



class Solution {
public:
    int dp[100010];
    unordered_map<int ,int> PrimesMinLen;

    int splitArray(vector<int>& nums) {
        memset(dp, 0x3f, sizeof dp);
        nums.insert(nums.begin(), 100019);
        dp[0] = 0;
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = dp[i - 1] + 1;  //另开一个数组
            //分解质因数
            int splitP[20]; memset(splitP, 0, sizeof splitP);
            int splitCnt = 0;
            for (int j = 2; j <= nums[i] / j; j++) {
                while (nums[i] % j == 0) {
                    nums[i] /= j;
                    splitP[splitCnt] = j;
                }
                if (splitP[splitCnt] != 0) {
                    int primesV = splitP[splitCnt]; splitCnt++;
                    if (PrimesMinLen.count(primesV) != 0)
                        dp[i] = min(dp[i], PrimesMinLen[primesV]+1);
                }
            }

            if (nums[i] != 1) {   
                splitP[splitCnt] = nums[i]; splitCnt++;
                int primesV = nums[i];
                if(PrimesMinLen.count(primesV) !=0)
                    dp[i] = min(dp[i], PrimesMinLen[primesV]+1);
            }
           
            //更新 该元素左端的元素 质数对应的最短分组
            for (int j = 0; j < splitCnt; j++) {
                int primesV = splitP[j];
                if (PrimesMinLen.count(primesV) == 0) PrimesMinLen[primesV] = dp[i-1];
                else PrimesMinLen[primesV] = min(PrimesMinLen[primesV], dp[i-1]);
            }
        }

        return dp[nums.size() - 1];
    }
};


int main()
{
    Solution s;
    vector<int> v{ 2,3,3,2,3,3 };
    cout << s.splitArray(v);
}
 